package problem04_12;

import java.util.HashMap;

//面试题04.12.求路劲和
//https://leetcode.cn/problems/paths-with-sum-lcci/

class Solution {
    int sum = 0, ret = 0;
    HashMap<Integer, Integer> map = new HashMap<>();
    public int pathSum(TreeNode root, int _sum) {
        map.put(0, 1);
        sum = _sum;
        dfs(root, 0);
        return ret;
    }

    public void dfs(TreeNode root, int s) {
        if(root == null) return;

        s += root.val;
        ret += map.getOrDefault(s - sum, 0);
        map.put(s, map.getOrDefault(s, 0) + 1);

        dfs(root.left, s);
        dfs(root.right, s);

        map.put(s, map.getOrDefault(s, 0) - 1);
        s -= root.val;
    }
}
